`
https://leetcode.cn/problems/minimum-cost-for-tickets/
`

/**
 * @param {number[]} days
 * @param {number[]} costs
 * @return {number}
 */
var mincostTickets = function (days, costs) {
  const memo = new Array(days.length).fill(-1)

  function dp(start) {
    if (start >= days.length) {
      return 0
    }

    if (memo[start] !== -1) {
      return memo[start]
    }

    const curDay = days[start]
    let nextIndex = start

    // 选择买 1 天的票
    while (nextIndex < days.length && days[nextIndex] < curDay + 1) {
      nextIndex++
    }
    const cost1day = dp(nextIndex) + costs[0]
    // 选择买 7 天的票
    while (nextIndex < days.length && days[nextIndex] < curDay + 7) {
      nextIndex++
    }
    const cost7day = dp(nextIndex) + costs[1]
    // 选择买 30 天的票
    while (nextIndex < days.length && days[nextIndex] < curDay + 30) {
      nextIndex++
    }
    const cost30day = dp(nextIndex) + costs[2]

    memo[start] = Math.min(cost1day, cost7day, cost30day)
    return memo[start]
  }

  return dp(0)
};